package book;

import java.util.Arrays;

public class NQueenSolution {
    // 回溯法求解n皇后问题
    public int queen(int n) {
        // x[i]表示第i行放置皇后的列下标，-1表示未放置      
        int[] x = new int[n];
        Arrays.fill(x, -1);
        int k = 0, count = 0;
        // 循环模拟递归，摆放皇后k
        while (k >= 0) {                           
            x[k]++;
            while (x[k] < n && checkPlace(k, x)) {
                x[k]++;
            }
            if (x[k] < n && k == n - 1) {
                for (int j = 0; j < n; j++) 
                    System.out.print(x[j] + 1 + "  ");
                System.out.println();
                ++count;
            }
            if (x[k] < n && k < n - 1) k = k + 1;
            else x[k--] = -1;
        }
        // 最后返回总共有多少组解
        return count;
    }

    // 检查皇后k放置在x[k]列是否发生冲突
    // 返回true表示产生冲突，不能放置
    // 返回false表示可以放置在该位置
    public boolean checkPlace(int k, int[] x) {     
        for (int i = 0; i < k; i++) {
            if (x[i] == x[k] || 
                Math.abs(i - k) == Math.abs(x[i] - x[k])) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int ans = new NQueenSolution().queen(4);
        System.out.println("共有 " + ans + " 个解!");
    }
}

